The present invention discloses, in general, a method and apparatus for traffic monitoring and controlling of a connection in packet communication networks. More specifically, the present invention provides a fuzzy leaky bucket mechanism for improving the performance in terms of selectivity, responsiveness, and mean queueing delay in ATM networks.
The emergence of multimedia services has diversified the bandwidth requirement for data communications. The asynchronous transfer mode (ATM) is considered as a suitable technique to meet the diverse bandwidth requirement since its design objectives are to support different types of traffic and multiple quality of services (QoS). To achieve the design objectives, several traffic control mechanisms are recommended for ATM networks [1]. Two of them are the call admission control (CAC) and the usage parameter control (UPC).
CAC is performed at the call setup phase of a new call to decide whether the new call can be accepted or not. It accepts the new call if the network can afford the required bandwidth and QoS of the new connection while the QoS of the already established connections can still be maintained. Then a traffic contract is made between the new connection and the network. The traffic contract contains traffic descriptors such as the peak cell rate (PCR), the sustainable cell rate (SCR) and the maximum burst size (MBS). For CAC to perform correctly, all the established connections must not violate their respective traffic contracts, which are of vital importance to the decision making of CAC. To make sure that the established connections conform to their respective traffic contracts, CAC is coupled with another traffic control mechanism, namely, UPC.
UPC is performed at the user-network interface (UNI) during the data transfer phase. It is defined as the set of actions taken by the network to monitor and control the offered traffic of a connection so that the corresponding traffic contract is respected. Its main purpose is to protect network resources from malicious as well as unintentional misbehavior, which can affect the QoS of other already, established connections. The wide variety of services with different traffic characteristics and QoS requirements makes UPC a difficult task. The difficulty lies in finding a simple, universal and effective UPC scheme, which is able to police any types of traffic ranging from video to data traffic. Several UPC schemes such as the jumping window, triggered jumping window, moving window, exponentially weighted moving average, and leaky bucket mechanisms were studied and compared [2-5]. The most popular and well-known policing scheme is the leaky bucket algorithm because of its simplicity and effectiveness.
Monitoring and controlling the peak cell rate of a connection is not difficult because we only have to determine if the peak emission interval is smaller than the reciprocal of the negotiated peak cell rate xcex9PCR. But monitoring and controlling the sustainable cell rate of a connection is much more complicated because the connection is eligible to transfer cells with a short-term mean rate higher than the negotiated sustainable cell rate xcex9SCR as long as the long-term mean rate of the connection conforms to xcex9SCR.
Usually, a traffic shaper (TS) is equipped within the customer premise equipment to regulate the cell stream of the traffic source so as to conform the negotiated SCR. The regulation is to alter the traffic characteristics of the cell stream to achieve a desired modification. The consequence of the modification is an increase in the mean cell transfer delay. The conjunction of TS and UPC, named as TS-UPC pair, should employ an identical scheme with same parameters settings so that any possible non-conforming cell that might have been detected as non-conforming by UPC will be detected ahead of time and saved in the queue by TS. In this way, the TS-UPC pair can guarantee zero cell loss ratio at UPC for a non-violating connection. Nevertheless, if a user intentionally or unintentionally changes the parameter settings in TS to enjoy a higher throughput there, UPC will detect the violation and take actions against it.
Three performance requirements have to be fulfilled by the TS-UPC pair:
(1.) High selectivity: UPC should detect the non-conforming cells of a violating connection as much as possible, while being transparent when the connection conforms to its traffic contract.
(2.) High responsiveness: the time for UPC to detect a violating connection should be rather short.
(3.) Low mean queueing delay: TS should not queue too many cells of a non-violating connection. However, the queueing delay introduced by TS on a violating connection is beyond the guarantee.
The primitive connection model with conventional TS-UPC pair is shown in FIG. 1. In a customer premise equipment 10, the component attached to the traffic source 12 is the TS 14, which contains a queue 16 and a shaper 18. The shaper 18 employs the conventional leaky bucket algorithm to determine the conformance of cells. It bypasses the conforming cells but stores the non-conforming cells in the queue for further legal transmission. The component at the entrance of the network 20 is the UPC 22 where a policer 24 is incorporated. The UPC 22 is connected to the customer premise equipment 10 through a UNI 30. The policer 24 also employs the conventional leaky bucket algorithm as the shaper 18 does. It bypasses the conforming cells but drops or tags the non-conforming cells. Despite the fact that the conventional leaky bucket algorithm is simple and effective, the conventional TS-UPC pair has performance defects such as long response time, low selectivity, and large mean queueing delay. One reason for the defects is its lack of system information such as the long-term mean cell rate of the connection, and another is its crisp structure with two fixed parameters of the threshold and the increment, which will be described later.
As specified in the ITU-T Recommendation I.371 document [1], dated May 1996, the Generic Cell Rate Algorithm (GCRA) is recommended as a conformance test for the cell stream of a connection. GCRA has two equivalent versions, the virtual scheduling algorithm and the leaky bucket algorithm. The latter seems to be better comprehended since it can be pictured as a virtual leaky bucket whose content determines the conformance of a cell. As shown in FIG. 2, the leaky bucket is viewed as a finite capacity bucket whose real-valued content drains out at one unit rate but is increased by T units for each conforming cell. If a cell arrives at the time ta when the bucket content Xxe2x80x2 is above the threshold value xcfx84, then the cell is non-conforming; otherwise, the cell is conforming and the bucket content is added by an increment T.
When the shaper 18 and the policer 24 in the TS-UPC pair shown in FIG. 1 employ the leaky bucket algorithm shown in FIG. 2 as their schemes to monitor the sustainable cell rate of a connection, the threshold value xcfx84 is taken to be xcfx84IBT+xcfx84xe2x80x2SCR and the increment T is taken to be the reciprocal of the negotiated sustainable cell rate xcex9SCR of the connection, where xcfx84IBT is the intrinsic burst tolerance (IBT) used to limit the burst size to the negotiated maximum burst size (MBS) and xcfx84xe2x80x2SCR is an additional tolerance added to account for the cell delay variation (CDV) introduced by multiplexing schemes. Details of the two parameters xcfx84IBT and xcfx84xe2x80x2SCR can be found in the ITU-T Recommendation I.371 [1]. The sustainable cell rate is used to enforce the mean cell rate of a connection, so it is straight forward to set xcex9SCR=xcex9mean for the TS-UPC pair, where xcex9mean is the mean cell rate claimed by the connection.
If xcex9SCR is set to be xcex9mean for the TS-UPC pair, then the possible rate fluctuations of the connection around the claimed mean cell rate will cause the leaky bucket within TS to detect some non-conforming cells. These detected non-conforming cells are stored in the queue, resulting in a long queueing delay. The undesirable long queueing delay can be avoided by making the bucket threshold xcfx84 in TS and UPC deviate from xcfx84IBT+xcfx84xe2x80x2SCR to a large value. Unfortunately, a higher xcfx84 would cause the slower response time for UPC. Another solution without changing the bucket threshold is to make xcex9SCR be xcex9mean multiplied by a magnifying factor C, C greater than 1. By doing this, we can eliminate the retardation provoked by a higher xcfx84. However, it has a risk of letting a connection with small rate fluctuations, e.g. a CBR connection, enjoy bandwidth higher than that negotiated. There are an infinite number of admissible couples of values for xcex9SCR and xcfx84. The detailed analysis for the selection of xcex9SCR and xcfx84 and the consequent system performance can be found in [6].
References [1-6] are hereby incorporated herein by reference.
In the present invention we consider a packet communication service discipline of the type with the TS-UPC pair as described in FIG. 1 and provide a mechanism incorporated a fuzzy leaky bucket scheme by which the sustainable cell rate of a connection is monitored and controlled optimally during the connection is sustained. The proposed mechanism can make a connection being policed in ATM networks achieve a better performance in terms of selectivity, responsiveness, and mean queueing delay.
The present invention describes a novel method and apparatus for implementation of a leaky bucket allowing adjustable increment for the leaky bucket content of a connection in ATM networks. In the present invention, we propose using fuzzy logic to improve the performance of the conventional leaky bucket mechanism. In one preferred embodiment, a fuzzy increment controller (FIC) is incorporated in the leaky bucket algorithm to dynamically adjust the increment for the leaky bucket content of the connection being policed. Preferably, two system parameters of the long-term mean cell rate and the short-term mean cell rate of the connection being policed are fed into the fuzzy increment controller to adaptively calculate an appropriate increment value with an aim to achieve a better performance.
The adjustment of the increment by the fuzzy logic is accomplished through a set of linguistic rules based upon a domain knowledge being as follows. When the cell stream of a connection appears to be violating the negotiated sustainable cell rate, the increment should be adjusted to be big so that the leaky bucket can quickly detect the non-conforming cells; while in contrast, when the cell stream of a connection appears to be conforming or conservative to the sustainable cell rate, the increment should be adjusted to be reasonably small so that no cell of the connection will be detected as non-conforming cells by the leaky bucket.
The leaky bucket algorithm with the fuzzy increment controller is herein called fuzzy leaky bucket algorithm, and a TS-UPC pair that employs the fuzzy leaky bucket algorithm is named as fuzzy TS-UPC pair. The fuzzy leaky bucket algorithm has the ability to quickly express the control structure of a system using a priori knowledge. Besides, it is less dependent on the availability of a precise model of the controlled process, and is more capable of handling nonlinearities. The present invention also provides simulation results to show that a fuzzy TS-UPC pair has a faster responsiveness and a higher selectivity than the conventional TS-UPC pair. In addition, the fuzzy TS-UPC pair introduces a much smaller mean queueing delay. It is also robust with respect to different traffic source models.